/*********************双向链表********************/

/**
 * 节点信息
 */
class Node {
    constructor(content, pre, next) {
        this.content = content;
        this.pre = pre;
        this.next = next;
    }
}

class DoubleLinkedList {
    constructor() {
        this.size = 0;
        // 头节点
        this.head = null;
        // 尾节点
        this.tail = null;
    }

    /**
     * 查找指定位置的元素
     * @param {索引位置} index 
     * @returns 
     */
    _node(index) {
        if (index < 0 || index >= this.size) {
            throw new Error('out of index');
        }
        let temp = this.size / 2;
        let retNode = null;
        if (temp > index) {
            retNode = this.head;
            for (let i = 0; i < index; i++) {
                retNode = retNode.next;
            }
        } else {
            retNode = this.tail;
            for (let i = this.size - 1; i > index; i--) {
                retNode = retNode.tail;
            }
        }
        return retNode;
    }

    /**
     * 添加元素
     * @param {索引} index 
     * @param {元素} element 
     */
    add(index, element) {
        if (arguments.length == 1) {
            element = index;
            index = this.size;
        }
        // 索引判断
        if (index < 0 || index > this.size) {
            throw new Error('out of index');
        }
        // 如果添加在尾部
        if (index == this.size) {
            let last = this.tail;
            let newNode = new Node(element, last, null);
            if (last === null) {
                // 如果添加的元素是第一个的情况
                this.head = newNode;
            } else {
                last.next = newNode;
            }
            this.tail = newNode;
        } else {
            // 获取到目标节点
            let target = this._node(index);
            // 前一个
            let pre = target.pre;
            let newNode = new Node(element, pre, target);
            target.pre = newNode;
            if (pre === null) {
                // 当前节点是第一个
                this.head = newNode;
            } else {
                pre.next = newNode;
            }
        }
        this.size++;
    }

    /**
     * 删除指定索引位置的元素
     * @param {索引信息} index 
     */
    remove(index) {
        if (index < 0 || index >= this.size) {
            throw new Error('out of index');
        }
        // 获取要删除的节点
        let target = this._node(index);
        let pre = target.pre;
        let next = target.next;

        if (pre == null) {
            // 删除的是头节点
            this.head = next;
        } else {
            pre.next = next;
        }
        if (next == null) {
            // 删除的是尾节点
            this.tail = pre;
        }else{
            next.pre = pre;
        }
        this.size --;
    }
    /**
     * 获取指定索引的节点信息
     * @param {索引} index 
     */
    get(index){
        return this._node(index);
    }

    /**
     * 清空链表
     */
    clear(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

let list = new DoubleLinkedList();
list.add(4);
list.add(5);
list.add(0, 1);
list.add(0, 2);
list.remove(1);
console.log(list);